class Solution
{
    int ans = INT_MIN;
    int dfs(TreeNode* root)
    {
        if (!root) return 0;
        int l = max(dfs(root->left), 0);
        int r = max(dfs(root->right), 0);

        ans = max(ans, root->val + l + r);

        return root->val + max(l, r);
    }
public:
    int maxPathSum(TreeNode* root)
    {
        dfs(root);
        return ans;
    }
};